import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

//优先级队列
public class Heap {

    int[] ele;
    int usedSize;
    public Heap(){
        ele = new int[10];
    }

    public void initHeap(int[] val){
        for (int i = 0; i < val.length; i++) {
            ele[i] = val[i];
            usedSize++;
        }
    }
    //创建大根堆
    public void creatHeap(int[] ele) {

        for (int parent = (ele.length - 1 - 1) >> 1; parent >= 0; parent--) {
            shitDown(parent);
        }

    }
    private void shitDown(int parent){
        int size = usedSize;
        int child = parent * 2 + 1;

        //进入循环，孩子的下标必须合法
        while (child < size) {

            //判断右孩子是否存在
            if (child + 1 < size && ele[child] < ele[child + 1]) {
                child = child + 1;
            }

            //判断根节点是否满足
            if (ele[parent] < ele[child]) {
                swap(parent, child);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }
        private void swap(int parent,int child){
            int tem = ele[parent];
            ele[parent] = ele[child];
            ele[child] = tem;
        }

        //增加元素
    public void offer(int val){
        //是否需要扩容
        if(usedSize == ele.length){
            extendCapacity();
        }
        //增加元素
        ele[usedSize] = val;
        //向上调整
        shitUp(usedSize);
        usedSize++;
    }
    private void shitUp(int child){
        int parent = (child - 1) / 2;
        while(child > 0){
            //判断
            if(ele[parent] < ele[child]) {
                //交换
                swap(parent, child);
            }
                //改变坐标
                child = parent;
                parent = (child -1) / 2;

        }
    }
    private boolean extendCapacity(){
        ele = Arrays.copyOf(ele,ele.length * 2);
        if(ele != null) return true;
        return false;
    }

    //去除队列元素
    public int poll(){
        if(isEmpty()) return -1;
        //交换元素
        int ret = ele[0];
        swap(0,usedSize - 1);
        usedSize--;
        shitDown(0);
        return ret;
    }
    private boolean isEmpty(){
        return usedSize == 0;
    }

    public int peek(){
        if(isEmpty()) return -1;

        return ele[0];
    }

    public int size(){
        return usedSize;
    }
    public void clear(){
        ele = null;
    }

    public int[] smallestK(int[] arr, int k) {
        if(k <= 0){
            return new int[0];
        }
        IntCmp intCmp = new IntCmp();
        PriorityQueue<Integer> q = new PriorityQueue<>(k,intCmp);
        for(int i = 0; i < arr.length; ++i){
            // 先使arr中前k个元素创建小堆
            if(i < k){
                q.offer(arr[i]);
            }else{
                // 使用堆顶与arr中剩余元素进行比较，如果arr[i]小于堆顶元素时，则替换堆顶元素
                if(intCmp.compare(arr[i], q.peek()) > 0){
                    q.poll();
                    q.offer(arr[i]);
                }
            }
        }
        // 堆中剩余的n个元素就是所要的k个元素
        int[] ret = new int[k];
        for(int i = 0; i < k; ++i){
            ret[i] = q.poll();
        }
        return ret;
    }

}
class IntCmp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}
